#include "SqList.h"

typedef struct TNode *Position;
typedef Position BinTree;

struct TNode {
    ElemType Data;
    BinTree Left;
    BinTree Right;
};

void InitList_T(BinTree &T) {
    T = NULL;
}

BinTree Insert(BinTree BST, ElemType book) {
    if (!BST) {
        BST = (BinTree) malloc(sizeof(struct TNode));
        BST->Data = book;
        BST->Left = BST->Right = NULL;
    } else {
        if (book.ISBN < BST->Data.ISBN)
            BST->Left = Insert(BST->Left, book);
        else if (book.ISBN > BST->Data.ISBN)
            BST->Right = Insert(BST->Right, book);
    }
    return BST;
}

Position FindMin(BinTree BST) {
    if (BST) {
        while (BST->Left)
            BST = BST->Left;
    }
    return BST;
}

Position FindMax(BinTree BST) {
    if (BST) {
        while (BST->Right)
            BST = BST->Right;
    }
    return BST;
}

BinTree Delete(BinTree &BST, ElemType book) {
    BinTree Tmp;
    if (!BST)
        printf("Not Found\n");
    else {
        if (book.ISBN < BST->Data.ISBN)
            BST->Left = Delete(BST->Left, book);
        else if (book.ISBN > BST->Data.ISBN)
            BST->Right = Delete(BST->Right, book);
        else {
            if (BST->Left && BST->Right) {
                Tmp = FindMin(BST->Right);
                BST->Data = Tmp->Data;
                BST->Right = Delete(BST->Right, BST->Data);
            } else {
                Tmp = BST;
                if (!BST->Left)
                    BST = BST->Right;
                else
                    BST = BST->Left;
                free(Tmp);
            }
        }
    }
    return BST;
}

Position Find(BinTree BST, ElemType book) {
    if (!BST)
        return NULL;
    if (book.ISBN > BST->Data.ISBN)
        return Find(BST->Right, book);
    else if (book.ISBN < BST->Data.ISBN)
        return Find(BST->Left, book);
    else
        return BST;
}

Position FindISBN(BinTree BST, int e) {
    // ö
    if (!BST)
        return NULL;
    if (e > BST->Data.ISBN)
        return FindISBN(BST->Right, e);
    else if (e < BST->Data.ISBN)
        return FindISBN(BST->Left, e);
    else
        return BST;
}